#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode *next;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class binarySearchTree {
public:
    bool isValidBST(TreeNode* root) {
        // 递归判断，左子树最大值 < 根节点值 < 右子树最小值
        return isValidBst(root, nullptr, nullptr);
    }

    bool isValidBst(TreeNode* root, TreeNode* min, TreeNode* max) {
        if (root == nullptr)
            return true;
        if (min != nullptr && root->val <= min->val)
            return false;
        if (max != nullptr && root->val >= max->val)
            return false;
        return isValidBst(root->left, min, root) && isValidBst(root->right, root, max);
    }

    bool isValidBSTNoRecursive(TreeNode* root) {
        // 利用栈实现中序遍历，判断是否升序
        if (root == nullptr)
            return true;
        long long maxVal = (long long)INT_MIN - 1;
        TreeNode* cur = root;
        stack<TreeNode *> sk;
        
        while (!sk.empty() || cur != nullptr) {
            while (cur != nullptr) {
                sk.push(cur);
                cur = cur->left;
            }
            
            cur = sk.top();
            sk.pop();
            if (maxVal >= cur->val)
                return false;
            maxVal = cur->val;
            cur = cur->right;
        }
        return true;
    }


    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == nullptr)
            return nullptr;
        if (root->val == val) 
            return root;
        else if (root->val > val)
            return searchBST(root->left, val);
        else 
            return searchBST(root->right, val);
    }

    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == nullptr)
            return new TreeNode(val);
        if (root->val > val) 
            root->left = insertIntoBST(root->left, val);
        else 
            root->right = insertIntoBST(root->right, val);
        return root;
    }

    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr)
            return nullptr;
        // 1.找到了
        if (root->val == key) {
            // 对nullptr的验证
            if (root->left == nullptr)
                return root->right;
            if (root->right == nullptr)
                return root->left;
            // 情况3，找右子树最小值替换
            root->val = findRightMin(root->right)->val;
            root->right = deleteNode(root->right, root->val);
        }
        // 2.没找到
        else if (root->val > key)
            root->left = deleteNode(root->left, key);
        else
            root->right = deleteNode(root->right, key);
        
        return root;
    }

    TreeNode* findRightMin(TreeNode* subRoot) {
        TreeNode *cur = subRoot;
        while (cur->left != nullptr) {
            cur = cur->left;
        }
        return cur;
    }

};